{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你单链表的头节点 <code>head</code> ，请你反转链表，并返回反转后的链表。\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg\" style=\"width: 542px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[5,4,3,2,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg\" style=\"width: 182px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2]\n",
    "<strong>输出：</strong>[2,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目范围是 <code>[0, 5000]</code></li>\n",
    "\t<li><code>-5000 <= Node.val <= 5000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？</p>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-linked-list](https://leetcode.cn/problems/reverse-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-linked-list](https://leetcode.cn/problems/reverse-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[1,2]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "        if m == 1:\n",
    "            return self.reverseList(head, n)\n",
    "        else:\n",
    "            head.next = self.reverseBetween(head.next, m - 1, n - 1)\n",
    "        return head\n",
    "\n",
    "    def reverseList(self, head: ListNode, n) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if not n:\n",
    "            return head\n",
    "        if n == 1:\n",
    "            self.next_normal = head.next\n",
    "            return head\n",
    "        last = self.reverseList(head.next, n - 1)\n",
    "        head.next.next = head\n",
    "        head.next = self.next_normal\n",
    "        return last\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        def reverseList(head,n):\n",
    "            if not head or not head.next: return head\n",
    "            if n==1: return head\n",
    "            cur = reverseList(head.next,n-1)\n",
    "            successor = head.next.next\n",
    "            head.next.next = head\n",
    "            head.next = successor\n",
    "            return cur\n",
    "        \n",
    "        if m==1: return reverseList(head,n)\n",
    "        head.next = self.reverseBetween(head.next,m-1,n-1)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre, current_node = None, head\n",
    "        while(current_node):\n",
    "            next_node = current_node.next\n",
    "            current_node.next = pre\n",
    "            pre = current_node\n",
    "            current_node = next_node\n",
    "        return pre\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "        new_head = None\n",
    "        head_next = head.next\n",
    "        while head and head_next :\n",
    "            head.next = new_head\n",
    "            new_head = head\n",
    "            head = head_next\n",
    "            head_next = head_next.next\n",
    "        head.next = new_head\n",
    "        new_head = head\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dummy = ListNode(0)\n",
    "        while head:\n",
    "            current_head, head_next, dummy_next = head, head.next, dummy.next\n",
    "            head = head.next\n",
    "            dummy.next = current_head\n",
    "            current_head.next = dummy_next\n",
    "        return dummy.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "        tail = head\n",
    "        prev = None\n",
    "        while tail:\n",
    "            temp = tail.next\n",
    "            tail.next = prev\n",
    "            prev = tail\n",
    "            tail = temp\n",
    "        return prev\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None:\n",
    "            return head\n",
    "        cur=head\n",
    "        pre=None        \n",
    "        beh=None\n",
    "        while cur!=None:\n",
    "            beh=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=beh\n",
    "        return pre\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        ret = ListNode(head.val)\n",
    "        while head!=None and head.next!=None:\n",
    "            node = ListNode(head.next.val)\n",
    "            head = head.next\n",
    "            node.next = ret\n",
    "            ret = node\n",
    "            \n",
    "        return ret\n",
    "#         node = self.reverseList(head.next)\n",
    "#         head.next = None\n",
    "#         ret = node\n",
    "#         while node.next!=None:\n",
    "#             node = node.next\n",
    "#         node.next = head\n",
    "        \n",
    "#         return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        rev0 = ListNode(head.val)\n",
    "        head = head.next\n",
    "        rev = rev0\n",
    "        while head:\n",
    "            rev = ListNode(head.val)\n",
    "            rev.next = rev0\n",
    "            rev0 = rev\n",
    "            head = head.next\n",
    "        return rev\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        ans = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if (head == None) or (head.next == None):\n",
    "            return head\n",
    "        else:\n",
    "            newhead = self.reverseList(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return newhead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        try:\n",
    "            if head.next is None:\n",
    "                return head\n",
    "\n",
    "            new_head = self.reverseList(head.next)\n",
    "\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return new_head\n",
    "        except AttributeError:\n",
    "            pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        ret = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        \n",
    "        node = self.reverseList(head.next)\n",
    "        head.next = None\n",
    "        ret = node\n",
    "        while node.next!=None:\n",
    "            node = node.next\n",
    "        node.next = head\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        tmp = self.reverseList(head.next) \n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return tmp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        p, rev = head, None\n",
    "        while p:\n",
    "            rev, rev.next, p = p, rev, p.next\n",
    "        return rev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        pre,cur=None,head\n",
    "        while cur:\n",
    "            tmp=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=tmp\n",
    "        return pre\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        first = dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        while head and head.next:\n",
    "            cur = head.next\n",
    "            head.next = cur.next\n",
    "            cur.next = dummy.next\n",
    "            dummy.next = cur\n",
    "        return first.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        p,rev = head,None\n",
    "        while p:\n",
    "            rev,rev.next, p = p, rev,p.next\n",
    "        return rev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "\n",
    "        while head is not None  and head.next is not None:\n",
    "            dnext = dummy.next\n",
    "            hnext = head.next\n",
    "            dummy.next = hnext\n",
    "            head.next = hnext.next\n",
    "            hnext.next = dnext\n",
    "            \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        ## 双指针\n",
    "        pre = None\n",
    "        cur = head\n",
    "\n",
    "        while cur:\n",
    "            temp = cur.next ## 需要首先将cur.next存储起来\n",
    "            cur.next = pre ## 转换方向\n",
    "            pre = cur \n",
    "            cur = temp\n",
    "        \n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # if head is None:\n",
    "        #     return None\n",
    "        # stack = []\n",
    "        # while head:\n",
    "        #     stack.append(head)\n",
    "        #     head = head.next\n",
    "        # for i in range(1, len(stack)):\n",
    "        #     stack[-i].next = stack[-i-1]\n",
    "        # return stack[-1]\n",
    "\n",
    "\n",
    "        # 一：迭代\n",
    "        prev = None\n",
    "        curr = head\n",
    "        # while curr:\n",
    "        #     nextTemp = curr.next;\n",
    "        #     curr.next = prev;\n",
    "        #     prev = curr;\n",
    "        #     curr = nextTemp; \n",
    "        while head:\n",
    "            head = head.next\n",
    "            curr.next = prev\n",
    "            prev = curr\n",
    "            print(prev.val)\n",
    "            curr = head\n",
    "        return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        tail = None\n",
    "        temp = head\n",
    "        while temp:\n",
    "            temp = head.next\n",
    "            head.next = tail\n",
    "            tail = head\n",
    "            head = temp\n",
    "            # tail.PrintListNode()\n",
    "        return tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "\n",
    "        p, rev = head, None\n",
    "        while p:\n",
    "            rev, rev.next, p = p, rev, p.next\n",
    "        return rev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        pre_node = None\n",
    "        cur_node = head\n",
    "        while cur_node != None:\n",
    "            tmp = cur_node.next\n",
    "            cur_node.next = pre_node\n",
    "            pre_node, cur_node = cur_node, tmp\n",
    "        return pre_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            next = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        last=None\n",
    "        cur=head\n",
    "        while cur:\n",
    "            tmp=cur.next\n",
    "            cur.next=last\n",
    "            last=cur\n",
    "            cur=tmp\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        while head:\n",
    "            print(head.val)\n",
    "            tmp = head.next\n",
    "            head.next = pre\n",
    "            pre = head\n",
    "            head = tmp\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prev = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = prev\n",
    "            prev = cur\n",
    "            cur = temp\n",
    "        return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            next = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            tmp = cur.next # 暂存后继节点 cur.next\n",
    "            cur.next = pre # 修改 next 引用指向\n",
    "            pre = cur      # pre 暂存 cur\n",
    "            cur = tmp      # cur 访问下一节点\n",
    "        return pre\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            tem = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tem\n",
    "        return pre\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        new_head = None\n",
    "        while head:\n",
    "            new_head = ListNode(head.val,new_head)\n",
    "            head = head.next\n",
    "        return new_head\n",
    "\n",
    "\n",
    "        # a_head = None\n",
    "        # new_head = ListNode(head.val,a_head)\n",
    "        # head = head.next\n",
    "        # new_head = ListNode(head.val,new_head)\n",
    "        # head = head.next\n",
    "        # new_head = ListNode(head.val,new_head)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 20231127_这些不行\n",
    "        # if head==None or head.next == None:\n",
    "        #     return head\n",
    " \n",
    "    \n",
    "\n",
    "        # c = self.reverseList(head.next)\n",
    "\n",
    "        # head.val,c.val = c.val ,head.val\n",
    "        # head.next = c\n",
    "\n",
    "        # return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 20231126 没通\n",
    "        # if head==None :\n",
    "        #     return head\n",
    "        # elif head.next == None:\n",
    "        #     return head.val\n",
    "        \n",
    "        # head.val,head.next = head.next,head.val\n",
    "\n",
    "        # return head\n",
    "\n",
    "        # if head  == None or type(head) is int or type(head.next) is int or  head is None:\n",
    "        #     return head\n",
    "        # print(head.val)\n",
    "        # print(head.next)\n",
    "        # print(head)\n",
    "        # if head == None:\n",
    "        #     return head \n",
    "        # if head.next == None:\n",
    "        #     print(\"==\",head)\n",
    "        #     return head \n",
    "        # print(head)\n",
    "        # print(head.val)\n",
    "        # print(head.next)\n",
    "\n",
    "        # a =  self.reverseList(head.next)\n",
    "\n",
    "        # head.val , head.next = a.val, a.next\n",
    "\n",
    "        # # return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(-1)\n",
    "        d = dummy\n",
    "        p = head\n",
    "        ans = []\n",
    "        while p:\n",
    "            ans.append(p.val)\n",
    "            p = p.next\n",
    "        for i in range(len(ans)):\n",
    "            d.next = ListNode(ans[-i-1])\n",
    "            d = d.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return head\n",
    "        a=[]\n",
    "        while(head):\n",
    "            a.append(head.val)\n",
    "            head=head.next\n",
    "        print(a)\n",
    "        c=b=ListNode(a[-1])\n",
    "        for i in range(len(a)-2,-1,-1):\n",
    "            print(i)\n",
    "            c.next=ListNode(a[i])\n",
    "            c=c.next\n",
    "        return b\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def exneib(header:ListNode,k:int,times:int):\n",
    "    sign=k-(2*times+1)\n",
    "    if(sign==0):\n",
    "        return header\n",
    "    if(sign==1):\n",
    "        test=header.next\n",
    "        test.next=header\n",
    "        header.next=None\n",
    "        return test\n",
    "    else:\n",
    "        times+=1\n",
    "        helper=0\n",
    "        test=header\n",
    "        while(helper<sign):\n",
    "            test=test.next\n",
    "            helper+=1\n",
    "        test.next=exneib(header.next,k,times)\n",
    "        elt=test\n",
    "        while(elt.next!=test and elt.next!=None):\n",
    "            elt=elt.next\n",
    "        elt.next=header\n",
    "        header.next=None\n",
    "        return test\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        helper=0\n",
    "        m=head\n",
    "        while(m!=None):\n",
    "            m=m.next\n",
    "            helper+=1\n",
    "        if(helper==0):\n",
    "            return head\n",
    "        head=exneib(head,helper,0)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        def reverseTopN(root,N):\n",
    "            if not root or N==0:\n",
    "                return None \n",
    "            if N==1:\n",
    "                return root\n",
    "            if N==2:\n",
    "                s1=root\n",
    "                s2=root.next\n",
    "                s3=s2.next\n",
    "                s1.next=s3\n",
    "                s2.next=s1\n",
    "                return s2\n",
    "            root.next=reverseTopN(root.next,N-2)\n",
    "            sec1=root\n",
    "            sec2=root.next\n",
    "            for i in range(N-2):\n",
    "                root=root.next\n",
    "            sec3=root\n",
    "            root=root.next\n",
    "            sec4=root\n",
    "            root=root.next\n",
    "            sec5=root\n",
    "            fake=ListNode()\n",
    "            sec4.next=None\n",
    "            sec1.next=None\n",
    "            fake.next=sec4\n",
    "            sec4.next=sec2\n",
    "            sec3.next=sec1\n",
    "            sec1.next=sec5\n",
    "            return fake.next\n",
    "        count=0\n",
    "        c=head\n",
    "        while(c):\n",
    "            c=c.next\n",
    "            count+=1\n",
    "        return reverseTopN(head,count)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "      \n",
    "      if not head or not head.next:\n",
    "        return head\n",
    "\n",
    "      newHead = ListNode(0)\n",
    "\n",
    "      newHead = self.reverseList(head.next)\n",
    "      head.next.next = head\n",
    "      head.next = None\n",
    "      return newHead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#递归法\n",
    "class Solution:\n",
    "  from typing import Optional\n",
    "  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:  \n",
    "    if(head==None or head.next==None):\n",
    "      return head\n",
    "    elif(head.next.next==None):\n",
    "      temp=head.next\n",
    "      temp.next=head\n",
    "      head.next=None\n",
    "      return temp\n",
    "    elif(head.next.next!=None):\n",
    "      first=head\n",
    "      second=head.next\n",
    "      third=head.next.next\n",
    "      third_reverse=self.reverseList(third)\n",
    "      #由于third_reverse为一个链表，其最后项肯定是之前正序时的第三个项，故前面的third就是third_reverse的末项\n",
    "      #所以不需要使用while从third_reverse中手动找到最后一项\n",
    "      third.next=second\n",
    "      second.next=first\n",
    "      first.next=None\n",
    "      return third_reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#递归法\n",
    "class Solution:\n",
    "  from typing import Optional\n",
    "  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:  \n",
    "    if(head==None or head.next==None):\n",
    "      return head\n",
    "    elif(head.next.next==None):\n",
    "      temp=head.next\n",
    "      temp.next=head\n",
    "      head.next=None\n",
    "      return temp\n",
    "    elif(head.next.next!=None):\n",
    "      first=head\n",
    "      second=head.next\n",
    "      third=head.next.next\n",
    "      third_reverse=self.reverseList(third)\n",
    "      #由于third_reverse为一个链表，其最后项肯定是之前正序时的第三个项，故前面的third就是third_reverse的末项\n",
    "      #所以不需要使用while从third_reverse中手动找到最后一项\n",
    "      third.next=second\n",
    "      second.next=first\n",
    "      first.next=None\n",
    "      return third_reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None: return head\n",
    "        temp = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        fake = ListNode(None)\n",
    "        fake.next  = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return fake.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(head: ListNode) -> ListNode:\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            last = reverse(head.next) \n",
    "            head.next.next = head \n",
    "            head.next = None \n",
    "            return last\n",
    "        return reverse(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        \n",
    "        p = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "\n",
    "        return p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        nex = head.next\n",
    "        res = self.reverseList(nex)\n",
    "        nex.next = head\n",
    "        head.next = None\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        cur = head\n",
    "        last = None\n",
    "        while cur:\n",
    "            last = cur\n",
    "            cur = cur.next\n",
    "        \n",
    "        print(last)\n",
    "\n",
    "        def recur(cur):\n",
    "            if not cur or not cur.next:\n",
    "                return cur\n",
    "            recur(cur.next)\n",
    "            cur.next.next = cur\n",
    "            cur.next = None\n",
    "        \n",
    "        recur(head)\n",
    "        return last\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(head):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            \n",
    "            last = reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return last\n",
    "\n",
    "        return reverse(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        last=self.reverseList(head.next)\n",
    "        head.next.next=head\n",
    "        head.next=None\n",
    "\n",
    "        return last"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
